POJ_2431

题解

贪心加优先队列。
每当油不够时，pop出经过的最大容量的加油站，加完油。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <stdio.h>
#include <queue>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=10010;
struct  stop
{
    int dis;
    int value;
}ss[MAXN];
bool cmp(stop a, stop b){
    return a.dis > b.dis;
}
int main()
{
    int n,l,p;
    while(~scanf("%d",&n)){
        for(int i=1;i<=n;i++)
            scanf("%d%d",&ss[i].dis,&ss[i].value);
        scanf("%d%d",&l,&p);
        ss[++n].value=0;
        ss[n].dis=0;
        sort(ss+1,ss+1+n,cmp);
        priority_queue<int > pque;
        int ans=0,pos=l,tank=p;
        for(int i=1;i<=n;i++){
            int d =  pos-ss[i].dis;
            while(tank - d < 0){
                if(pque.empty()){
                    ans = -1;
                    break;
                }
                tank += pque.top();
                pque.pop();
                ans++;
            }
            if(ans == -1)break;
            tank -= d;
            pos=ss[i].dis;
            pque.push(ss[i].value);
        }
        printf("%d\n",ans);
    }
    return 0;
}